package basic.study.leetcode;

/**
 * @ClassName Easy234
 * @Description 回文链表
 * @Company inspur
 * @Author Kevin
 * @Date 2020/7/9 9:55
 * @Version 1.0
 */
public class Easy234 {
    class Solution {
        public boolean isPalindrome(ListNode head) {
            if (head == null) return true;

            ListNode fast = head;
            ListNode slow = head;
            ListNode pre = null;

            while (fast != null && fast.next != null) {
                fast = fast.next.next;
                ListNode next = slow.next;
                slow.next = pre;
                pre = slow;
                slow = next;
            }
            if (fast != null) {
                slow = slow.next;
            }

            while (slow != null) {
                if (slow.val != pre.val) {
                    return false;
                }
                slow = slow.next;
                pre = pre.next;
            }
            return true;
        }
    }

    class ListNode {
        int val;
        ListNode next;
        public ListNode(int val) {
            this.val = val;
        }
    }
}
